/*!
 Temelia - Sparse matrix interface.

 For-each row and column I keep a red black tree. Nodes are
 compare via their index - each node contains an index and user's key.

 For example m[i,j] is stored at ith red black tree in a node
 that hold pair of {j, m[i][j]}.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef SPARSE_MATRIX_H_
#define SPARSE_MATRIX_H_

#include "common.h"

struct _sparse_matrix_t;
typedef struct _sparse_matrix_t *sparse_matrix_t;

struct _sparse_matrix_key_t;
typedef struct _sparse_matrix_key_t *sparse_matrix_key_t;

#define SPARSE_MATRIX_ROW_DENSE        (1 << 2)
#define SPARSE_MATRIX_COLUMN_DENSE     (1 << 3)

/*
 * Constructor/destructor
 */
DECLSPEC sparse_matrix_key_t sparse_matrix_key_new(void *user_key, int index);
DECLSPEC void sparse_matrix_key_delete(sparse_matrix_key_t key);
DECLSPEC sparse_matrix_key_t sparse_matrix_key_duplicate(sparse_matrix_key_t key);

/*
 * Get/set method for [index, user key] stored, as pair, in sparse matrix key
 */
DECLSPEC int sparse_matrix_key_get_index(sparse_matrix_key_t key);
DECLSPEC void *sparse_matrix_key_get_key(sparse_matrix_key_t key);
DECLSPEC void sparse_matrix_key_set_index(sparse_matrix_key_t key, int index);
DECLSPEC void sparse_matrix_key_set_key(sparse_matrix_key_t key, void *user_key);

/*!
 * @brief Returns an empty sparse_matrix.
 * Complexity O(1)
 *
 * @param Rows number
 * @param Columns number
 * @param Maximum number of not null keys
 * @param Type of sparse matrix. Current available parameters are SPARSE_MATRIX_ROW_DENSE
 * and SPARSE_MATRIX_COLUMN_DENSE; depending on the type, sparse matrix will use
 * red black trees to store rows and columns. If both parameters are passed
 * (SPARSE_MATRIX_ROW_DENSE | SPARSE_MATRIX_COLUMN_DENSE) then the pointers
 * are stored in mirror
 */
DECLSPEC sparse_matrix_t sparse_matrix_new(int rows, int columns, int size, int type);

/*!
 * @brief Duplicates a sparse_matrix
 * Complexity O(size)
 *
 * @param Sparse_matrix
 */
DECLSPEC sparse_matrix_t sparse_matrix_clone(sparse_matrix_t sparse_matrix);

/*!
 * @brief Frees the memory occupied by sparse_matrix.
 * Complexity O(size)
 *
 * @param Sparse matrix
 */
DECLSPEC void sparse_matrix_delete(sparse_matrix_t sparse_matrix);

/*!
 * @brief Checks if current sparse matrix is empty.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_is_empty(sparse_matrix_t sparse_matrix);

/*!
 * @brief Checks if current sparse matrix is full.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_is_full(sparse_matrix_t sparse_matrix);

/*!
 * @brief Sets key value at position in sparse_matrix. You can use this function
 * to add an key or to update it's value.
 * Complexity O(rows + columns)
 *
 * @param Sparse matrix
 * @param Row
 * @param Column
 * @param Key
 */
DECLSPEC void sparse_matrix_set_key_at(sparse_matrix_t sparse_matrix, int row,
		int column, void *key);

/*!
 * @brief Returns key at position in a sparse_matrix.
 * Complexity O(min(rows, columns))
 *
 * @param Sparse matrix
 * @param Row
 * @param Column
 * @param Additional info about the distribution of matrix elements; -1
 * for row dense matrix, 1 for column dense matrix and 0 if you don't
 * have any opinion about your matrix
 */
DECLSPEC void *sparse_matrix_get_key_at(sparse_matrix_t sparse_matrix, int row,
		int column, int preference);

/*!
 * @brief Removes the key at position in a sparse_matrix; it also calls
 * the destructor of pair.
 * Complexity O(rows + columns)
 *
 * @param Sparse matrix
 * @param Row
 * @param Column
 */
DECLSPEC void sparse_matrix_remove_key_at(sparse_matrix_t sparse_matrix, int row,
		int column);

/*!
 * @brief Returns number of sparse matrix's rows.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_get_rows_number(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns number of sparse_matrix's columns.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_get_columns_number(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns the maximum not null keys, that can be stored, in this
 * sparse matrix.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_get_size(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns the type of sparse matrix.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_get_type(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns the current not null elements number.
 * Complexity O(1)
 *
 * @param Sparse matrix
 */
DECLSPEC int sparse_matrix_get_not_null_keys(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns the keys internal representation of rows.
 * In current implementation is a red_black_tree_t with
 * pair_t as elements. Each pair consists of column index and user's key.
 *
 * @param Sparse matrix
 */
DECLSPEC void *sparse_matrix_get_rows(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns the keys internal representation of columns.
 * In current implementation is a red_black_tree_t with
 * pair_t as elements. Each pair consists of row index and user's key.
 *
 * @param Sparse matrix
 */
DECLSPEC void *sparse_matrix_get_columns(sparse_matrix_t sparse_matrix);

/*!
 * @brief Returns transposed sparse_matrix.
 * @param Sparse matrix
 */
DECLSPEC sparse_matrix_t sparse_matrix_transpose(sparse_matrix_t sparse_matrix);

/*!
 * @brief Iterates over the keys of the current sparse_matrix.
 * Depending on the order this function will call first on columns and
 * then on rows or first on rows.
 * Complexity O(size)
 *
 * @param Sparse matrix
 * @param Handling function
 * @param Context
 * @param Order; 1 first on columns and then on rows, -1 first on rows and then on columns
 */
DECLSPEC void sparse_matrix_iterate(sparse_matrix_t sparse_matrix, void key_handler(
		void *key, int row, int column, void *context), void *context,
		int order);

/*!
 * @brief Resized sparse matrix to new dimensions: (rows, columns, maximum size)
 * Complexity O(rows + columns)
 *
 * @param Sparse matrix
 * @param New rows number
 * @param New columns number
 * @param New maximum size
 */
DECLSPEC void sparse_matrix_resize(sparse_matrix_t sparse_matrix, int rows, int columns, int size);

#endif /* SPARSE_MATRIX_H_ */
